import ckmeans from 'ckmeans';

// ---------- 工具 ----------
function minMaxFast(arr) {
  let min = Infinity, max = -Infinity;
  for (let i = 0; i < arr.length; ++i) {
    const v = arr[i];
    if (v < min) min = v;
    if (v > max) max = v;
  }
  return [min, max];
}

// 升序快排（百万级够用）
function quickSort(arr) {
  if (arr.length <= 1) return arr;
  const pivot = arr[arr.length >> 1];
  const left = [], right = [], mid = [];
  for (const v of arr) {
    if (v < pivot) left.push(v);
    else if (v > pivot) right.push(v);
    else mid.push(v);
  }
  return [...quickSort(left), ...mid, ...quickSort(right)];
}

// IQR 法过滤
function iqrFilter(arr, kFactor = 1.5) {
  const sorted = quickSort(arr);
  const n = sorted.length;
  const q1 = sorted[Math.floor(n * 0.25)];
  const q3 = sorted[Math.floor(n * 0.75)];
  const iqr = q3 - q1;
  const low  = q1 - kFactor * iqr;
  const high = q3 + kFactor * iqr;
  return arr.filter(v => v >= low && v <= high); // 保留 99% 正常区间
}

// ---------- 主函数 ----------
function robustJenks(data, k, binCount = 512, iqrK = 1.5) {
  // 1. 过滤异常值
  const clean = iqrFilter(data, iqrK);

  // 2. 对干净数据做直方图
  const [min, max] = minMaxFast(clean);
  console.log(min, max);
  const step = (max - min) / binCount;
  const hist = new Array(binCount).fill(0);
  clean.forEach(v => {
    const idx = Math.min(binCount - 1, Math.floor((v - min) / step));
    hist[idx]++;
  });

  // 3. ckmeans
  const centers = hist.map((_, i) => min + step * (i + 0.5));
  const clusters = ckmeans(centers, k, hist);
  console.log(clusters)
  // 4. 生成断点（簇与簇之间）
  const breaks = [];
  // for (let i = 0; i < clusters.length - 1; ++i) {
  //   const last = clusters[i][clusters[i].length - 1];
  //   const next = clusters[i + 1][0];
  //   breaks.push((last + next) / 2);
  // }

  // 5. 返回：断点 + 完整坐标范围（用于画图）
  const [realMin, realMax] = minMaxFast(data);// 原始极值
  
  return { breaks: clusters, axis: [realMin, realMax] };
}

/* ==== DEMO ==== */
const big = Array.from({ length: 1_000_000 }, () => Math.random() * 1000);
const test = [...big, 100_000, -10002]; // 混入极端值
console.log(robustJenks(test, 5));